package com.zhm.demo.hash;


import cn.hutool.core.util.StrUtil;

import java.util.*;

public class ConsistentHashingWithVirtualNode {

    //真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
    private Set<String> realNodes = new TreeSet<>();
    //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    private SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
    //虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
    private static final int VIRTUAL_NODES = 5;


    //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
    private int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }

    //得到应当路由到的结点
    private String getServer(String key) {
        //得到该key的hash值
        int hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }
        //virtualNode虚拟节点名称要截取一下
        if (StrUtil.isNotBlank(virtualNode)) {
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        return null;
    }

    private boolean addServer(String server) {
        //先把原始的服务器添加到真实结点列表中
        boolean addRes = realNodes.add(server);
        if (addRes) {
            //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
            for (int j = 0; j < VIRTUAL_NODES; j++) {
                String virtualNodeName = server + "&&VN" + String.valueOf(j);
                int hash = getHash(virtualNodeName);
                //System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        return addRes;
    }

    private boolean removeServer(String server) {
        boolean removeRes = realNodes.remove(server);
        if (removeRes) {
            for (int j = 0; j < VIRTUAL_NODES; j++) {
                String virtualNodeName = server + "&&VN" + String.valueOf(j);
                int hash = getHash(virtualNodeName);
                virtualNodes.remove(hash);
            }
        }
        return removeRes;
    }

    public void allServer(Collection<String> servers) {
        servers.forEach(server -> {
            allServer(servers);
        });
        realNodes.forEach(server -> {
            if (!realNodes.contains(server)) {
                removeServer(server);
            }
        });
    }


    public static void main(String[] args) {
        ConsistentHashingWithVirtualNode consistentHashingWithVirtualNode = new ConsistentHashingWithVirtualNode();
        //程序初始化，将所有的服务器放入sortedMap中
        for (int i = 0; i < 100; i++) {
            String server = "192.168.0." + i + ":111";

            if (i > 90) {
                int j = (i - 1);
                consistentHashingWithVirtualNode.removeServer("192.168.0." + j + ":111");
            }

            System.out.println(consistentHashingWithVirtualNode.addServer(server));

            String[] keys = {
                    "太阳1", "月亮2", "星星33"};
            for (int j = 0; j < keys.length; j++) {
                System.out.println("[" + keys[j] + "]的hash值为" + consistentHashingWithVirtualNode.getHash(keys[j])
                        + ", 被路由到结点[" + consistentHashingWithVirtualNode.getServer(keys[j]) + "]");
            }

            System.out.println("------------------------------");
        }
    }

}
